Multiplicativity of the Legendre Symbol
Theorem
\[ \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]
Proof
This follows from the formula for the Legendre symbol using Euler's criterion
\[\begin{align*}
\left(\frac{ab}{p}\right) &= (ab)^{\frac{p - 1}{2}} \mod p \\
&= a^{\frac{p - 1}{2}} b^{\frac{p - 1}{2}} \mod p \\
&= (a^{\frac{p - 1}{2}} \mod p)(b^{\frac{p - 1}{2}} \mod p) & a^{\frac{p - 1}{2}}, b^{\frac{p - 1}{2}} \equiv \pm 1 \pmod p \\
&= \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
\end{align*}\]